//给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [
//ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。 
//
// 请你返回 无法互相到达 的不同 点对数目 。 
//
// 
//
// 示例 1： 
//
// 
//
// 输入：n = 3, edges = [[0,1],[0,2],[1,2]]
//输出：0
//解释：所有点都能互相到达，意味着没有点对无法互相到达，所以我们返回 0 。
// 
//
// 示例 2： 
//
// 
//
// 输入：n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
//输出：14
//解释：总共有 14 个点对互相无法到达：
//[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6]
//,[5,6]]
//所以我们返回 14 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 10⁵ 
// 0 <= edges.length <= 2 * 10⁵ 
// edges[i].length == 2 
// 0 <= ai, bi < n 
// ai != bi 
// 不会有重复边。 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 图 👍 136 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//java:统计无向图中无法互相到达点对数
public class Q2316CountUnreachablePairsOfNodesInAnUndirectedGraph {
    public static void main(String[] args){
        Solution solution = new Q2316CountUnreachablePairsOfNodesInAnUndirectedGraph().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    // 邻接矩阵
    List<Integer>[] adjArr;
    // 标记是否遍历过
    boolean[] visited;
    public long countPairs(int n, int[][] edges) {
        long res = 0;
        adjArr = new ArrayList[n];
        visited = new boolean[n];
        // 创建邻接矩阵
        for (int i = 0; i < n; i++) {
            adjArr[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adjArr[edge[0]].add(edge[1]);
            adjArr[edge[1]].add(edge[0]);
        }


        //用一个变量 total 维护前面求出的连通块的大小之和
        for (int i = 0, total = 0; i < n; i++) {
            // 未访问的点：说明找到了一个新的连通块
            if (!visited[i]) {
                int size = dfs(i);
                // 设当前连通块的大小为 size，那么这个连通块中的每个点，
                // 与前面遍历过的连通块的每个点，都是无法互相到达的，根据乘法原理，这有 size⋅total 个，
                res += (long) size * total;
                total += size;
            }
        }
        return res;
    }

    // 统计每个块的大小
    public int dfs(int x) {
        visited[x] = true;
        int size = 1;
        for (int y : adjArr[x]) {
            // 防止重复访问
            if (!visited[y]) {
                size += dfs(y);
            }
        }
        return size;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}